package com.txy.sort;

public class HeapSort {
    public static void sort(int []arr) {
        for(int i =arr.length/2-1;i>=0;i--) {
            adjustHeap(arr, i ,arr.length);
        }
        for(int i=arr.length-1;i>0;i--) {
            int tmp = arr[i];
            arr[i]=arr[0];
            arr[0]=tmp;
            adjustHeap(arr, 0, i);
        }
    }

    private static void adjustHeap(int[] arr, int parent, int len) {
        int tmp = arr[parent];
        int child = 2*parent+1;
        while(child < len){
            if(child+1<len && arr[child+1]>arr[child]) {
                child ++;
            }
            if(tmp >= arr[child]) {
                break;
            }
            arr[parent] = arr[child];
            parent = child;
            child = child*2+1;
        }
        arr[parent]=tmp;
    }
}
